package org.wuxinshui.boosters.nowcoder.classicQuestion;


/**
 * 使用插入排序对链表进行排序。
 * 输入：{30,20,40}
 * 返回值：{20,30,40}
 */
public class CC5InsertionSortList_Practice {
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 创建虚拟头节点，简化边界处理
        ListNode dummy = new ListNode(0);
        // curr 指向当前待插入的节点
        ListNode curr = head;

        while (curr != null) {
            // 保存下一个待处理节点
            ListNode nextTemp = curr.next;

            // 在已排序部分中找到插入位置
            ListNode prev = dummy;
            ListNode sortedCurr = dummy.next;

            // 寻找第一个大于等于当前节点值的位置
            while (sortedCurr != null && sortedCurr.val < curr.val) {
                prev = sortedCurr;
                sortedCurr = sortedCurr.next;
            }

            // 插入当前节点到正确位置
            curr.next = sortedCurr;
            prev.next = curr;

            // 移动到下一个待处理节点
            curr = nextTemp;
        }

        return dummy.next;
    }


    // 优化版本：减少比较次数
    public ListNode insertionSortListOptimized(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        ListNode lastSorted = dummy; // 指向已排序部分的最后一个节点

        ListNode curr = head;

        while (curr != null) {
            ListNode nextTemp = curr.next;

            // 如果当前节点值大于等于已排序部分的最后一个节点，直接接在后面
            if (curr.val >= lastSorted.val) {
                lastSorted.next = curr;
                curr.next = null;
                lastSorted = curr;
            } else {
                // 否则需要在已排序部分中找到插入位置
                ListNode prev = dummy;
                ListNode sortedCurr = dummy.next;

                while (sortedCurr != null && sortedCurr.val < curr.val) {
                    prev = sortedCurr;
                    sortedCurr = sortedCurr.next;
                }

                // 插入当前节点
                curr.next = sortedCurr;
                prev.next = curr;
            }

            curr = nextTemp;
        }

        return dummy.next;
    }

    // 测试代码
    public static void main(String[] args) {
        CC5InsertionSortList_Practice sorter = new CC5InsertionSortList_Practice();

        // 测试用例 1: 随机顺序
        ListNode head1 = createList(new int[]{4, 2, 1, 3});
        System.out.println("测试用例 1 - 随机顺序:");
        System.out.print("原始链表: ");
        printList(head1);
        ListNode sorted1 = sorter.insertionSortList(head1);
        System.out.print("排序后: ");
        printList(sorted1);
        System.out.println();

        // 测试用例 2: 逆序
        ListNode head2 = createList(new int[]{5, 4, 3, 2, 1});
        System.out.println("测试用例 2 - 逆序:");
        System.out.print("原始链表: ");
        printList(head2);
        ListNode sorted2 = sorter.insertionSortList(head2);
        System.out.print("排序后: ");
        printList(sorted2);
        System.out.println();

        // 测试用例 3: 已排序
        ListNode head3 = createList(new int[]{1, 2, 3, 4, 5});
        System.out.println("测试用例 3 - 已排序:");
        System.out.print("原始链表: ");
        printList(head3);
        ListNode sorted3 = sorter.insertionSortList(head3);
        System.out.print("排序后: ");
        printList(sorted3);
        System.out.println();

        // 测试用例 4: 包含重复元素
        ListNode head4 = createList(new int[]{3, 1, 4, 1, 5, 9, 2, 6});
        System.out.println("测试用例 4 - 包含重复元素:");
        System.out.print("原始链表: ");
        printList(head4);
        ListNode sorted4 = sorter.insertionSortListOptimized(head4);
        System.out.print("排序后: ");
        printList(sorted4);
    }

    // 创建链表
    private static ListNode createList(int[] values) {
        if (values == null || values.length == 0) return null;

        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        for (int val : values) {
            curr.next = new ListNode(val);
            curr = curr.next;
        }
        return dummy.next;
    }

    // 打印链表
    private static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) {
                System.out.print(" -> ");
            }
            head = head.next;
        }
        System.out.println();
    }
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
